from typing import List


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m = len(heights)
        n = len(heights[0])

        visited = [[False] * n for _ in range(m)]
        res = float("inf")
        print(m, n)

        def check(x, y):
            if x >= 0 and y >= 0 and x < m and y < n:
                return True
            else:
                return False

        def helper(x, y, value):
            nonlocal res
            print(x, y, res)
            # if not check(x, y) or visited[x][y]:
            #     return
            if x == m - 1 and y == n - 1:
                res = min(res, value)

            # height = heights[x][y]
            # value = abs(height - value)
            if value > res:
                return
            visited[x][y] = True

            if check(x + 1, y) and not visited[x + 1][y]:
                helper(x + 1, y, max(value, abs(heights[x + 1][y] - heights[x][y])))

            if check(x - 1, y) and not visited[x - 1][y]:
                helper(x - 1, y, max(value, abs(heights[x - 1][y] - heights[x][y])))

            if check(x, y + 1) and not visited[x][y + 1]:
                helper(x, y + 1, max(value, abs(heights[x][y + 1] - heights[x][y])))

            if check(x, y - 1) and not visited[x][y - 1]:
                helper(x, y - 1, max(value, abs(heights[x][y - 1] - heights[x][y])))

            visited[x][y] = False

        helper(0, 0, 0)

        return res


if __name__ == "__main__":
    heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]
    r = Solution().minimumEffortPath(heights)
    print(r)
